package com.leo.datastruct.sort;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月02日
 */
public class QuickSort extends Sortable {

    public QuickSort(String sortMethodName) {
        super(sortMethodName);
    }

    @Override
    public void sort(int[] s) {
        sort1(s, 0, s.length-1);
    }

    private void sort1(int[] s, int start, int end){
        if (start < end){
            int mid = partition(s, start, end);
            sort1(s, start, mid-1);
            sort1(s, mid+1, end);
        }
    }

    /**
     * 一趟排序
     * @param s
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] s, int start, int end){
        int temp = s[start];
        while (start < end){
            while (start < end && s[end]>=temp) {end--;}
            s[start]=s[end];
            while (start < end && s[start]<=temp) {start++;}
            s[end] = s[start];
        }
        s[start] = temp;
        return start;
    }

    public static void main(String[] args) {
        Sortable a = new QuickSort("快排");
        a.testSort(new int[]{49,38,65,97,76,13,27,49,78,34,12,64,1});
    }
}
